package phaseII;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

public class LL1Parser 
{
	private LL1Table table;
	
	private Symbol init;
	
	private ArrayList<Nonterminal> nonterminals;
	private ArrayList<Token> tokens;
	private ArrayList<Rule> rules;
	
	private HashMap<Nonterminal, ArrayList<Rule>> prerules;
	private HashMap<Nonterminal, ArrayList<Token>> firstsets;
	private HashMap<Nonterminal, ArrayList<Token>> followsets;
	private HashMap<Rule, ArrayList<Token>> predictsets;
	
	public LL1Parser()
	{
		init = null;
		
		nonterminals = new ArrayList<Nonterminal>();
		tokens = new ArrayList<Token>();
		rules = new ArrayList<Rule>();
		
		prerules = new HashMap<Nonterminal, ArrayList<Rule>>();
		firstsets = new HashMap<Nonterminal, ArrayList<Token>>();
		followsets = new HashMap<Nonterminal, ArrayList<Token>>();
		predictsets = new HashMap<Rule, ArrayList<Token>>();
	}
	
	public Symbol getInit()
	{
		return init;
	}
	
	public void printRules()
	{
		for (Nonterminal n : prerules.keySet()) 
		{
            for (Rule x : prerules.get(n)) 
                System.out.println(x);
        }
	}
	
	public void readInGrammarFile(String filename) throws IOException, FileNotFoundException
	{
		BufferedReader br = new BufferedReader(new FileReader(filename));
		String token, nonterminal, gr;
		ArrayList<String> grammarrules = new ArrayList<String>();
		ArrayList<Nonterminal> k = new ArrayList<Nonterminal>();
		
		token = br.readLine(); //%Tokens%, throws them all in tokens
		java.util.Scanner a = new java.util.Scanner(token);
		a.next();
		
		while (a.hasNext())
			tokens.add(new Token(a.next()));
		
		nonterminal = br.readLine();
		
		if (nonterminal.trim().equals(""))
			nonterminal = br.readLine();
		
		a = new java.util.Scanner(nonterminal);
		a.next(); //%nonterminals
		
		while (a.hasNext())
			nonterminals.add(new Nonterminal(a.next()));
			
		gr = br.readLine();
		
		
		if (gr.trim().equals(""))
			gr = br.readLine();
		//start symbol:
		
		init = new Symbol(gr.substring(gr.indexOf(" ") + 1, gr.indexOf('>') + 1));
		
		do
		{
			if (gr != null)
			{
				if (!gr.startsWith("%") && !gr.trim().equals(""))
					grammarrules.add(gr);	
			}
		} while ((gr = br.readLine()) != null);
		
		
		prerules = removeLeftRecursion(grammarrules);
		
		//printRules(); // shows rules after removing left recursion
		
		prerules = removeCommonPrefix(prerules);
		//printRules(); // shows rules after removing common prefixes
		
		k.addAll(prerules.keySet());
		for (Nonterminal b : k)
		{
			rules.addAll(prerules.get(b));
			if (!nonterminals.contains(b))
				nonterminals.add(b);
		}
	}

	public LL1Table createLL1Table()
	{
		ArrayList<Token> q = new ArrayList<Token>();
		Rule rn;
		
		boolean nullable = true;
		boolean follow = true;
		
		//first sets
		for (Nonterminal n : nonterminals)
		{
			ArrayList<Token> tmp = calcfirst(n);
			firstsets.put(n, tmp);
		}
		//end first sets
		
		//follow sets
		for (Nonterminal n2 : nonterminals)
		{
			if (!(n2.toString().equals(init.toString())))
				followsets.put(n2, new ArrayList<Token>());
			else
			{
				ArrayList<Token> tmp2 = new ArrayList<Token>();
				tmp2.add(new Token("$"));
				followsets.put(n2, tmp2);
			}
		}
		
		while (follow)
		{
			follow = false;
			for (Nonterminal nn : nonterminals)
			{
				for (Rule r : prerules.get(nn))
				{
					ArrayList<Symbol> elements = r.getRules();
					
					for (int x = 0; x < elements.size(); x++)
					{
						Symbol s = elements.get(x);
						nullable = true;
						
						if (s instanceof Nonterminal)
						{
							Nonterminal f = (Nonterminal) s;
							ArrayList<Token> followlist = followsets.get(f);
							ArrayList<Symbol> eor = new ArrayList<Symbol>(elements.subList(x+1, elements.size()));
							
							for (Symbol s2 : eor)
							{
								if (s2 instanceof Token && !s2.toString().equals("<epsilon>"))
									nullable = false;
								if (s2 instanceof Nonterminal)
								{
									if (!firstsets.get((Nonterminal) s2).contains(new Token("<epsilon>")))
										nullable = false;
								}
							}
							
							if (nullable)
							{
								ArrayList<Token> followlist2 = followsets.get(nn);
								for (Token t : followlist2)
								{
									if (!followlist.contains(t))
									{
										follow = true;
										followlist.add(t);
									}
								}
							}
							
							ArrayList<Symbol> followsyms = new ArrayList<Symbol>(elements.subList(x+1, elements.size()));
							//changed up firstcalculator for followsets
							ArrayList<Token> first = new ArrayList<Token>();
							if (followsyms.size() == 0)
							{
								//do nothing
							}
							else if (followsyms.size() == 1 && followsyms.contains(new Token("<epsilon>")))
								first.add(new Token("<epsilon>"));
							else
							{
								HashSet<Token> h = new HashSet<Token>();
								ArrayList<Token> initsym = calcfirst(followsyms.get(0));
								h.addAll(initsym);
								
								boolean hasep = h.contains(new Token("<epsilon>"));
								h.remove(new Token("<epsilon>"));
								int j = 1;
								
								while (hasep && j < followsyms.size())
								{
									ArrayList<Token> nextfirst = null;
									Symbol next = followsyms.get(j);
									
									if (next instanceof Nonterminal)
										nextfirst = firstsets.get((Nonterminal) next);
									else
										nextfirst = calcfirst(next);
									
									if (!nextfirst.contains(new Token("<epsilon>")))
										hasep = false;
									
									for (Token tt : nextfirst)
										h.add(tt);
									
									h.remove(new Token("<epsilon>"));
									j++;
								}
								
								first.addAll(h);
							}
							//end changeup
							
							for (Token t2 : first)
							{
								if (!followlist.contains(t2))
								{
									follow = true;
									followlist.add(t2);
								}
							}
							followsets.put(f, followlist);
						}
					}
				}
			}
		}
		//end follow sets
		
		//predict sets
		for (Rule r : rules)
		{
			ArrayList<Token> tmp3 = new ArrayList<Token>();
			
			ArrayList<Symbol> a = r.getRules();
			Nonterminal non = r.getNonterminal();
			
			//modified first set computer
			ArrayList<Token> first2 = new ArrayList<Token>();
			if (a.size() == 0)
			{
				//do nothing
			}
			//else if (a.size() == 1 && a.contains(new Token("<epsilon>")))
				//first2.add(new Token("<epsilon>"));
			else
			{
				HashSet<Token> h = new HashSet<Token>();
				ArrayList<Token> initsym = calcfirst(a.get(0));
				h.addAll(initsym);
				
				boolean hasep = h.contains(new Token("<epsilon>"));
				h.remove(new Token("<epsilon>"));
				int j = 1;
				
				while (hasep && j < a.size())
				{
					ArrayList<Token> nextfirst = null;
					Symbol next = a.get(j);
					
					if (next instanceof Nonterminal)
						nextfirst = firstsets.get((Nonterminal) next);
					else
						nextfirst = calcfirst(next);
					
					if (!nextfirst.contains(new Token("<epsilon>")))
						hasep = false;
					
					for (Token tt : nextfirst)
						h.add(tt);
					
					h.remove(new Token("<epsilon>"));
					j++;
				}
				
				first2.addAll(h);
			}
			//end mfsc
			
			for (Token t4 : first2)
				tmp3.add(t4);
			
			if (first2.contains(new Token("<epsilon>")))
			{
				for (Token t5 : followsets.get(non))
					tmp3.add(t5);
			}
			
			predictsets.put(r, tmp3);
		}
		//end predict sets
		
		table = new LL1Table(tokens, nonterminals, nonterminals.size(), tokens.size());
		
		Collection ruless = predictsets.keySet();
		Iterator i = ruless.iterator();
		
		while (i.hasNext())
		{
			rn = (Rule) i.next();
			q = predictsets.get(rn);
			
			for (Token t6 : q)
				table.add(rn.getNonterminal(), t6, rn);
		}
		
		return table;
	}
	
	private HashMap<Nonterminal, ArrayList<Rule>> removeCommonPrefix(HashMap<Nonterminal, ArrayList<Rule>> a)
	{
		boolean c = false;
		boolean contains = false;
		boolean bad = false;
		int maxsize = 0;
		
		ArrayList<Symbol> newrules = new ArrayList<Symbol>();
		ArrayList<Symbol> nnr = new ArrayList<Symbol>();
		ArrayList<Symbol> max = null;
		
		ArrayList<Rule> commonprefixrules;
		ArrayList<Rule> rc = new ArrayList<Rule>();
		
		ArrayList<Nonterminal> k = new ArrayList<Nonterminal>();
		k.addAll(a.keySet());
		for (Nonterminal x : k)
		{
			ArrayList<Rule> matches = a.get(x);
			ArrayList<Symbol> commonprefixes = new ArrayList<Symbol>();
			
			//get the max common prefix rules available
			if (matches.size() <= 1)
				commonprefixrules = new ArrayList<Rule>();
			else
			{
				ArrayList<ArrayList<Symbol>> fpref = new ArrayList<ArrayList<Symbol>>();
				for (Rule q : matches)
				{
					for (Rule w : matches)
					{
						ArrayList<Symbol> cp = new ArrayList<Symbol>();
						getCommon(cp, q.getRules(), w.getRules());
						//check to see if it contains the prefix
						for (ArrayList<Symbol> contained : fpref)
						{
							if (cp.equals(contained))
								contains = true;
						}
						
						if (!contains)
						{
							if (cp.size() > 0)
								fpref.add(cp);
						}
					}
				}
				//get the prefix of max length
				for (ArrayList<Symbol> e : fpref)
				{
					if (maxsize < e.size())
					{
						max = e;
						maxsize = e.size();
					}
				}
				// get all rules starting with a specific prefix
				if (max != null)
				{
					commonprefixes.addAll(max);
					for (Rule u : matches)
					{
						bad = false;
						if (u.getRules().size() >= max.size())
						{
							for (int qq = 0; qq < max.size() - 1; qq++)
							{
								if(!max.get(qq).equals(u.getRules().get(qq)) && !bad)
									bad = true;
							}
							
							if (!bad)
								rc.add(u);
						}
					}
				}
				// dump it into common prefix rules and voila
				commonprefixrules = rc;
			}

			if (commonprefixrules.size() >= 2)
			{
				Nonterminal n = new Nonterminal(x.toString() + x.toString().hashCode());
				
				newrules.addAll(commonprefixes);
				newrules.add(n);
				
				Rule newrule = new Rule(x, newrules);
				matches.removeAll(commonprefixrules);
				matches.add(newrule);
				
				ArrayList<Rule> nrules = new ArrayList<Rule>();
				
				for (Rule r : commonprefixrules)
				{
					for (int y = commonprefixes.size(); y < r.getRules().size(); y++)
						nnr.add(r.getRules().get(y));
					if(nnr.size() == 0)
						nnr.add(new Token("<epsilon>"));
				}
				a.put(n, nrules);
				c = true;
			}
		}
		
		if (c)
			removeCommonPrefix(a);
		else
			return a;
		
		return null;
	}
	
	private void getCommon(ArrayList<Symbol> cp, ArrayList<Symbol> r1, ArrayList<Symbol> r2)
	{
		ArrayList<Symbol> rr1 = new ArrayList<Symbol>(r1);
		ArrayList<Symbol> rr2 = new ArrayList<Symbol>(r2);
		
		if (r1.size() > 0 && r2.size() > 0 && !r1.equals(r2))
		{
			if (r1.get(0).equals(r2.get(0)))
			{
				rr1.remove(0);
				rr2.remove(0);
				cp.add(r1.get(0));
				getCommon(cp, rr1, rr2);
			}
		}
	}

	private HashMap<Nonterminal, ArrayList<Rule>> removeLeftRecursion(ArrayList<String> grammarrules)
	{
		int n = 0;
		
		ArrayList<Rule> r = new ArrayList<Rule>();
		ArrayList<Rule> matches;
		
		ArrayList<Nonterminal> k = new ArrayList<Nonterminal>();
		
		HashMap<Nonterminal, ArrayList<Rule>> h = new HashMap<Nonterminal, ArrayList<Rule>>();
		Nonterminal nts;
		
		for (String line : grammarrules)
		{
			ArrayList<Rule> generated = getRulesFrom(line);
			r.addAll(generated);
		}
		//hash rules by their nonterminals
		n = 0;
		while (n < r.size())
		{
			nts = r.get(n).getNonterminal();
			ArrayList<Rule> rr = new ArrayList<Rule>();
			while (r.get(n).getNonterminal().toString().equals(nts.toString()))
			{
				rr.add(r.get(n));
				n++;
				if (n == r.size())
					break;
			}
			h.put(nts, rr);
		}
		
		k.addAll(h.keySet());
		
		for (Nonterminal x : k)
		{
			matches = h.get(x);
			//test to see if the nonterminal has left recursion
			boolean nthasleftrecursion = false;
			
			for (Rule g : matches)
			{
				if (g.getRules().size() != 0)
				{
					
					if(g.getNonterminal().equals(x))
						nthasleftrecursion = true;
				}
			}
			
			if (nthasleftrecursion)
			{
				ArrayList<Rule> matches2 = (ArrayList<Rule>) matches.clone();
				
				Nonterminal p = new Nonterminal(x.toString()+"'");
				Rule peps = new Rule(p, new ArrayList<Symbol>());
				peps.getRules().add(new Token("<epsilon>"));
				
				ArrayList<Rule> pr = new ArrayList<Rule>();
				pr.add(peps);
				
				h.put(p, pr);
				
				for (Rule i : matches2)
				{
					Symbol first = i.getNonterminal();
					
					ArrayList<Symbol> nr = new ArrayList<Symbol>();
					nr.addAll(i.getRules());
					nr.add(p);
					matches.remove(i);
					
					if (first.equals(x) && i.getRules().size() > 0)
					{
						i.getRules().remove(0);
						pr.add(new Rule(p, nr));
					}
					else
						matches.add(new Rule(x, nr));
				}
			}
		}
		
		return h;
	}
	
	private ArrayList<Rule> getRulesFrom(String grammarrules)
	{
		String left, right;
		String[] individualrules;
		int i;
		ArrayList<Rule> generatedrules = new ArrayList<Rule>();
		
		i = grammarrules.indexOf("::=");
		left = grammarrules.substring(0, i);
		right = grammarrules.substring(i+3);
		individualrules = right.split("\\|", -1);
		
		Nonterminal n = new Nonterminal(left.trim());
		
		for (String x : individualrules)
		{
			ArrayList<Symbol> rside = new ArrayList<Symbol>();
			
			String r = x.trim();
			
			if (r.equals(""))
				rside.add(new Token("<epsilon>"));
			else
			{
				java.util.Scanner sc = new java.util.Scanner (r);
				while (sc.hasNext())
				{
					String c = sc.next().trim();
					
					if (tokens.contains(new Token(c)))
						rside.add(new Token(c));
					else if(nonterminals.contains(new Nonterminal(c)))
						rside.add(new Nonterminal(c));
				}
			}
			generatedrules.add(new Rule(n, rside));
		}
		return generatedrules;
	}
	
	private ArrayList<Token> calcfirst(Symbol s)
	{
		ArrayList<Token> terminal = new ArrayList<Token>();
		HashSet<Token> h = new HashSet<Token>();
		//hashsets are handy for ignoring duplicates
		
		if (s instanceof Token)
			terminal.add((Token) s);
		else
		{
			//System.out.println(prerules.toString());
			for (Rule w : prerules.get((Nonterminal)s))
			{
				boolean eps = false;
				ArrayList<Symbol> syms = w.getRules();
				
				for (Symbol e : syms)
				{
					eps = false;
					
					for (Token t : calcfirst(e))
					{
						if (!(t.toString().equals("<epsilon>")))
							h.add(t);
						else
							eps = true;
					}
					
					if (!eps)
						break;
				}
				
				if (eps)
					h.add(new Token("<epsilon>"));
			}
			terminal.addAll(h);
		}
		return terminal;
	}	
}
